package Offer136;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 要求算法具有线性时间复杂度
 * @author 23737
 * @time 2021.11.2
 */
public class Test {
    public static void main(String[] args) {
        int[] a = new int[]{1,1,2,2,30};
        int[] b = new int[]{1,1,2,2,30};
        int[] c = new int[]{1,1,2,2,30};
        System.out.println(new Solution().singleNumber(a));
        System.out.println(new Solution().singleNumber2(b));
        System.out.println(new Solution().singleNumber3(c));
    }
}

class Solution {
    /**
     * 使用hashmap
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
            Integer value = integerIntegerEntry.getValue();
            if (value == 1) return integerIntegerEntry.getKey();
        }
        return 0;
    }

    /**
     * 算是暴力法吧
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++, i++) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        if (nums.length %2 != 0) {
            return nums[nums.length - 1];
        }
        return 0;
    }

    /**
     * 神圣的满足要求的位运算
     * @param nums
     * @return
     */
    public int singleNumber3(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

}
